package algorithm.niuke;

public class H实现Trie前缀树 {
    /*
     * 实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
     * 
     * 示例:
     * 
     * Trie trie = new Trie();
     * 
     * trie.insert("apple"); trie.search("apple"); // 返回 true
     * trie.search("app"); // 返回 false trie.startsWith("app"); // 返回 true
     * trie.insert("app"); trie.search("app"); // 返回 true 说明:
     * 
     * 你可以假设所有的输入都是由小写字母 a-z 构成的。 保证所有输入均为非空字符串
     */
    public static class Trie {
        boolean log = true;
        Trie[] nodes = new Trie[26];
        boolean isStr = false;

        /** Initialize your data structure here. */
        public Trie() {

        }

        /** Inserts a word into the trie. */
        public void insert(String word) {
            if (word.length() < 1) {
                this.isStr = true;
                return;
            }
            char[] chs = word.toCharArray();
            char first = chs[0];
            int index = first - 'a';
            Trie node = nodes[index];
            if (node == null) {
                node = new Trie();
            }
            node.insert(word.substring(1, word.length()));
            nodes[index] = node;
        }

        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            if (word.length() < 1) {
                return isStr;
            }
            char[] chs = word.toCharArray();
            char first = chs[0];
            int index = first - 'a';
            Trie node = nodes[index];
            if (node == null) {
                return false;
            }
            return node.search(word.substring(1, word.length()));
        }

        /**
         * Returns if there is any word in the trie that starts with the given
         * prefix.
         */
        public boolean startsWith(String prefix) {
            if (log) {
                System.out.println(prefix);
            }
            if (prefix.length() < 1) {
                return true;
            }
            char[] chs = prefix.toCharArray();
            char first = chs[0];
            int index = first - 'a';
            Trie node = nodes[index];
            if (node == null) {
                return false;
            }
            return node.startsWith(prefix.substring(1, prefix.length()));
        }
    }

    /**
     * Your Trie object will be instantiated and called as such: Trie obj = new
     * Trie(); obj.insert(word); boolean param_2 = obj.search(word); boolean
     * param_3 = obj.startsWith(prefix);
     */
}
